1. Field of the Invention
The present invention relates to error correction coding and/or cipher systems used in the transmission of digital data. More specifically, the present invention relates to transforming input values to output values using non-linear, 1:1 mapping.
2. Related Prior Art Systems
Both error correction coding and ciphering systems usually include a digital logic circuit for transforming digital information bitstreams or data blocks, prior to transmission, into coded or ciphered blocks, respectively, in which each transformed bit depends on several of the original information bits. When used for error correction coding, such a circuit ensures that the original information bits can be effectively recovered even if transmission errors corrupt one or more of the transformed bits, since each of the original information bits is represented by a number of transformed bits. When used for ciphering, such a circuit protects the transmitted data (i.e., the original information bits if no error coding is used, or the transformed bits if error coding is used) from unintended reception by "masking" or disguising the data. This is typically performed by bitwise Exclusive ORing the information bits or the transformed bits with masking bits possessed only by the transmitter and the intended receiver. These masking bits are usually generated from a predetermined number of bits, commonly known as the "key" bits, which are applied to a pseudo-random process that sequentially produces various combinations of the key bits for use as masking bits.
It can thus be seen that both coding and ciphering require a mechanism to produce a multi-bit output in which each of the bits is a function of a multi-bit input. To obtain this "scrambling" of input bits, the prior art has used linear feedback shift registers, non-linear feedback shift registers and look-up tables including so-called "one-time pads". FIG. 1 illustrates a prior art linear feedback shift register, while FIG. 2 illustrates a non-linear feedback shift register. In FIG. 1, the linear feedback shift register comprises an N-stage shift register 10 the contents of which may be shifted one place to the right by applying a clock pulse to each the N stages. As well known in the art, each the N stages in the shift register 10 may be implemented with a D-type flip-flop having a clock input, a one-bit data input and a one-bit data output. For convenience and simplicity, the individual clock input to, and the separate one-bit input/output (I/O) of, each of these flip-flops are shown generally by arrows in FIG. 1.
As can be seen from FIG. 1, the input to the leftmost (N-1) flip-flop receives the output of a combinatorial logic circuit 20 (shown by dashed box) comprising Exclusive OR (XOR) gates 22, 24 and 26, which combine the outputs of selected flip-flops in the shift register 10. The current output of the XOR gate 26 becomes the next input to the N-1 flip-flop after the application of each new clock pulse. It will be appreciated that since the combinatorial logic circuit 20 is comprised strictly of the XOR gates 22, 24 and 26, each of which performs a linear modulo-2 addition, the output bit from the XOR gate 26, which is fed back to the input of the leftmost stage in the shift register 10 of FIG. 1, is a linear combination of certain selected contents of the shift register 10. In FIG. 2, however, the feedback input bit to the shift register 10 is formed by a combinatorial logic circuit 30 (within dashed box) which includes not only linear combinatorial logic consisting of XOR gates 32 and 38, but also non-linear combinatorial logic consisting of an AND gate 34 and OR gates 36 and 40. Thus, the output of the OR gate 40, which is fed back to the input of the leftmost stage in the shift register 10 of FIG. 2, is a non-linear combination of certain contents of the shift register 10.
Both the linear feedback shift register of FIG. 1 and the non-linear feedback shift register of FIG. 2 may be used to form desired logical functions of a number of input bits by first loading the input bits into the shift register 10 through the I/O ports, then shifting the register contents a defined number of times by applying a corresponding number of clock pulses to the clock ports, and finally extracting the scrambled contents from the I/O ports. Each bit of the extracted output would then represent one of the desired logical functions of the original input bits. Each of the linear and non-linear feedback shift registers, however, has its own advantages and disadvantages, as described below.
An advantage of the linear feedback shift register is the ability to accurately predict the maximum number of clock pulses that can be applied before the extracted output bit pattern begins to repeat, which is not always possible for the non-linear feedback shift register. As well known in the art, the maximum cycle length for an N-stage (N-bit) linear feedback shift register is 2.sup.N-1. This means that, for a particular starting state (N-bit value), the shift register 10 will cycle through 2.sup.N-1 states (different N-bit values) before returning to its initial state. In general, the actual cycle length for a linear feedback shift register is a function of both the number of input bits and the location of the output bits (taps) used to generate the feedback bit, and is usually somewhat less than the maximum cycle length. Non-linear feedback shift registers, on the other hand, sometimes exhibit significantly shorter cycle lengths called "short cycles," which are undesirable as they undermine the effectiveness of masking, for example. Such short cycles can be avoided, however, by using a linear feedback shift register as shown in FIG. 1, for example, and carefully choosing the taps which are used to form the feedback bit (with the caveat that an all-zeros input value be avoided since that would result in a short cycle of length 1, as the output value will be all zeroes regardless of the number of clock pulses applied).
Another advantage of linear feedback shift registers is that they perform what is known as a "1:1 mapping" or "information-lossless" transformation. The term "1:1 mapping" means that, for each possible pattern of input bits, there is a unique corresponding pattern of output bits. It is thus theoretically possible to reverse the transformation and determine what pattern of input bits caused a particular output pattern. The term "information lossless" also applies because the original input information can be totally recovered. The mapping performed by non-linear feedback shift registers, however, is not necessarily 1:1, but often MANY:1. This means that several different input bit patterns may transform to the same output pattern. Such a mapping process is not unambiguously reversible and, hence, a knowledge of the output state does not guarantee that the original input state can be deduced. In other words, such a process may be "information lossy."
A disadvantage of linear feedback shift registers, on the other hand, is the relative ease with which information ciphered using such registers can be recovered by an unintended receiver. Given a particular sequence of output bits detected at the receiver, it is possible to determine the internal configuration (i.e., which taps were used to form the feedback bit) for the register which generated this output and, thus, to reconstruct both the register and the original input information. Such reconstruction is more difficult in the case of a non-linear feedback shift register, and may require an uneconomic amount of computation. The enhanced security advantage associated with using non-linear feedback shift registers for ciphering derives from the same properties of these registers which, in the other contexts described above, were deemed to be a disadvantage (e.g., the MANY:1 mapping). Conversely, the reduced security disadvantage of linear feedback shift registers in the ciphering context derives from the same properties of those registers which, in the other contexts described above, were deemed to be an advantage (e.g., the 1:1 mapping). Clearly, it would be desirable to combine the advantages of both linear and non-linear feedback shift registers while avoiding their attendant disadvantages.
One approach to providing a non-linear mapping of input to output, which is yet guaranteed to be 1:1, is to use a so-called substitution box (S-box) or look-up table. When the number of input bits N is small (e.g., 4-16), a table of unique outputs corresponding to the 2.sup.N possible inputs may be stored in a memory. Thus, for 4-bit inputs, the memory would store 16 output patterns, while for 16-bit inputs, the memory would have to store 65,536 output patterns. Memory size and cost, of course, set a practical limit to the use of S-boxes. In principle, the contents of an S-box may be chosen completely at random, as long as no output pattern is used more than once, in order to preserve the desirable 1:1 relationship.
An early implementation of S-boxes was seen in manual ciphering systems in which books of input patterns and corresponding output patterns, known as "one-time pads," were provided to a transmitting correspondent and a receiving correspondent. After using a page of patterns in the book for ciphering or deciphering a message, the page was to be torn out and destroyed. Human error, however, often resulted in the incorrect use of one-time pads and in an abrogation of the intended security. For modern applications, such as protecting against the unauthorized reception of cellular radiotelephone calls, automatic electronic systems are needed. Such a system is provided by the present invention.